package algorithm.unionfind;

/**
 * @Description:
 * @Author Ammar
 * @Create 2023/5/17 11:10
 */
public class QuickUnion extends AbstractUnionFind {

    public QuickUnion(int capacity) {
        super(capacity);
    }

    @Override
    public int find(int v) {
        rangeCheck(v);
        // 向上超找根节点
        while (v != parents[v]) {
            v = parents[v];
        }
        return v;
    }

    @Override
    public void union(int v1, int v2) {
        int p1 = find(v1);
        int p2 = find(v2);
        if (p1 == p2) return;
        // 将p1的根节点嫁接到p2的根节点上
        parents[p1] = p2;
    }
}
